iT邦幫忙

2021 iThome 鐵人賽

DAY 3
0

為了解釋時間跟空間的取捨,來一條leetcode的題目,就是最經典的第一題Two Sum

輸入一組array、數值target,請從array中尋找兩個數字加總是等於tartget,並回傳array對應的index。
(兩個index不可重複、只會有一個答案)

ex 1.
Input: nums = [2,7,11,15], target = 9
Output: [0,1] (nums[0] + nums[1] == 9)

ex 2.
Input: nums = [3,2,4], target = 6
Output: [1,2] (nums[1] + nums[2] == 6)

如果你沒做過這題,強烈建議你先思考一下怎麼解。


防雷
防雷
防雷


最直覺的暴力解
跑兩次迴圈,每一個數值都跟其他數值加總一次
如果剛好等於target就回傳出去
時間複雜度為O(n^2)
註. 你可能會想,如果它剛好在迴圈的前幾次就找到答案了,那時間複雜度還是O(n^2)嗎?
-我們討論時間複雜度都會取最差的case,如果找不到target,這一段程式會完整跑完n*n。

func twoSum(nums []int, target int) []int {
	for i, v := range nums {
		for j, v2 := range nums {
			if i == j {
				continue
			}

			if v+v2 == target {
				return []int{i, j}
			}
		}
	}

	return nil
}

那存在時間複雜度為O(n)的解法嗎?
有的,這時候可以用hash map來解

nums = [2,7,11,15], target = 9
多一個map來記,key存值,val存index
跑一個迴圈,每一個值減去target,如果剛好在map找得到對應的key,那就是答案了。

ex.
index: 0, val: 2, map:{}
map[9-2] // 找不到

把2存到map裡面
map:{
	2: 0,
}

index: 1, val: 7
map[9-7] // 從map找到2 index是0 回傳[0,1]出去

程式:

func twoSum(nums []int, target int) []int {
	hash := make(map[int]int)
	for i, n := range nums {
		if j, ok := hash[target-n]; ok {
			return []int{j, i}
		}

		hash[n] = i
	}

	return nil
}

時間的複雜度從O(n^2)降低為O(n),但空間複雜度從O(1)升為O(n)。空間換時間或時間換空間,是很常有的情況,像是為了節省撈取DB的時間,所以做快取在記憶體,或者DB多記一些統計的欄位,避免重複的計算。

但是這取捨並非絕對!!如果這題的array有排序過,那會有另外一種解法,時間的複雜為O(n),但空間複雜度維持O(1)。

明天講!byebye


上一篇
Day.2 什麼是時間、空間複雜度?
下一篇
Day.4 Two Pointer
系列文
算法30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言